package com.atguigu.algorithm;

public class RabinKarp3 {
    static final long seed=31;

    public static void main(String[] args) {
        String s="ABABABA";
        String p="ABA";
        match(p,s);
    }

    static long hash(String str){
        long hash=0;
        for(int i=0;i<str.length();i++){
            hash=hash*seed+str.charAt(i);
        }
        return hash;
    }
    public static void match(String src,String dest){
        long hash1=hash(src);
        int len=src.length();
        long hash2=hash(dest.substring(0,len));
        for(int i=0;i+len<=dest.length();i++){
            if(hash2==hash1){
                System.out.println("match"+i);
            }
            hash2=hash2-dest.charAt(i)*(long)Math.pow(seed,len-1);
            hash2*=seed;
            hash2+=dest.charAt(i+1);
        }
    }
}
/*
* ABC    65*31^2+66*31+67
* BCD    66*31^2+67*31+68
* */

